package cn.edu.jxau.test;

import cn.edu.jxau.util.LinkedQueue;
import cn.edu.jxau.util.Queue;

/**
 * 找到和顶点start连通的所有顶点
 * 核心是并查集
 * 
 * @author 付大石
 */
public class Search {

    public static void main(String[] args) {

        UnionFind uf = new UnionFind(13);

        uf.union(0, 5);
        uf.union(4, 3);
        uf.union(0, 1);
        uf.union(9, 12);
        uf.union(6, 4);
        uf.union(5, 4);
        uf.union(0, 2);
        uf.union(11, 12);
        uf.union(9, 10);
        uf.union(0, 6);
        uf.union(7, 8);
        uf.union(9, 11);
        uf.union(5, 3);
        uf.union(6, 7); //增加这两个边后会变成连通图
        uf.union(8, 9);
        Search search = new Search(uf, 0);
//        Search search = new Search(uf,9);
        // 打印与对于顶点相连通的顶点 //
        for (int i = 0; i < 13; i++) {
            if (search.marked(i)) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
        if (search.count() == 13) {
            System.out.println("这是一个连通图");
        } else {
            System.out.println("这不是一个连通图");
        }
    }

    private boolean[] marked;
    private int count;

    public Search(UnionFind uf, int start) {
        marked = new boolean[uf.size()];
        mark(uf, start);
    }

    private void mark(UnionFind uf, int start) {
        
        for(int i=0;i<uf.size();i++) {
            if(uf.connected(i,start)) {
                marked[i] = true;
                count++;
            }
        }
    }

    public boolean marked(int v) {
        return marked[v];
    }

    public int count() {
        return count;
    }
}

/**
 * 加权quick-union的并查集
 * @author 付大石
 */
class UnionFind {

    /**
     * 并查集触点
     */
    private int[] id;

    /**
     * 触点的权重
     */
    private int[] weight;

    /**
     * 连通分量的个数
     */
    private int count;

    public UnionFind(int n) {

        this.count = n;
        id = new int[n];
        weight = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
            weight[i] = 1;
        }
    }

    /**
     * 返回连通分量的个数
     * @return
     */
    public int count() {
        return count;
    }

    /**
     * 返回触点的个数
     * @return
     */
    public int size() {
        return id.length;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 获取触点p所在的连通分量
     * @param p
     * @return
     */
    public int find(int p) {

        while (p != id[p]) { // 向上追溯找到根节点
            p = id[p];
        }
        return p;
    }

    public void union(int p, int q) {

        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) { // p、q已连接
            return;
        }
        if (weight[rootP] < weight[rootQ]) { // 连通分量q的权重较大,将p连到q上
            id[rootP] = rootQ;
            weight[rootQ] += weight[rootP];
        } else {
            id[rootQ] = rootP;
            weight[rootP] += weight[rootQ];
        }
        count--;
    }

}
